package com.zhang.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author Lelezhang
 * @create 2019-11-29 22:41
 */
public class BubbleSort {
    public static void main(String[] args) {
        //冒泡排序实现,事件复杂度o(n^2),n是数组长度,两次for循环
        //创建数据
        int[] arr = {5, 1, 12, -5, 16};
        System.out.println("排序前:" + Arrays.toString(arr));
        //调用冒泡排序
        int[] result = bubbleSort(arr);
        //输出结果
        System.out.println("排序后:" + Arrays.toString(result));

        //测试10W数据时间
        int[] testArr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            testArr[i] =(int)(Math.random()*1000000);
         }

        //耗时约17s
       /* long start = System.currentTimeMillis() / 1000;
        bubbleSort(testArr);
        long end = System.currentTimeMillis() / 1000;
        System.out.println("10W数据冒泡排序优化前耗时:"+(end-start)+" s");*/

        long start = System.currentTimeMillis() / 1000;
        bubbleSort(testArr);
        long end = System.currentTimeMillis() / 1000;
        System.out.println("10W数据冒泡排序优化后耗时:"+(end-start)+" s");
    }

    //冒泡排序,给出一个数组,耗时约40s
    public static int[] bubbleSort(int[] arr) {
        //创建一个临时变量,用于交换
        int temp = 0;
        //两两比较,需要比较arr.length - 1轮
        for (int i = 0; i < arr.length - 1; i++) {
            //每轮要比较arr.length - 1 - i次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //左边大于右边,则进行交换
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    //冒泡排序,给出一个数组,给出优化,避免一轮中一次交换也没有,但是又继续遍历
    public static int[] bubbleSort01(int[] arr) {
        //创建一个临时变量,用于交换
        int temp = 0;
        //定义标识,是否交换过
        boolean flag = false;
        //两两比较,需要比较arr.length - 1轮
        for (int i = 0; i < arr.length - 1; i++) {
            //每轮要比较arr.length - 1 - i次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //左边大于右边,则进行交换
                if (arr[j] > arr[j + 1]) {
                    //如果有交换则更改标识
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                //本轮比较,没有发生过交换,说明顺序已经是正确的结束循环
                if(!flag) {
                    break;
                }else {
                    //有交换进行下轮比较,标识复原
                    flag = false;
                }
            }
        }
        return arr;
    }
}
